# 473 中等：火柴拼正方形

# 回溯
def makeSquare(matchsticks):
    tol = sum(matchsticks)
    if tol % 4:
        return False
    matchsticks.sort(reverse=True)
    edges = [0] * 4

    def dfs(x):
        if x == len(matchsticks):
            return True
        for i in range(4):
            edges[i] += matchsticks[x]
            if edges[i] <= tol // 4 and dfs(x + 1):
                return True
            edges[i] -= matchsticks[x]
        return False

    return dfs(0)


print(makeSquare([1, 1, 2, 2, 2]))
